package arrays;

/**题目：小岛数量
 * y:
 *      1   0   0
 *      0   1   1
 *      0   1   1
 *
 * 小岛数量为2（一个1或者连通起来都是1的都计数为一个小岛，0表示海水）
 * @Author Gavin
 * @date 2022.01.11 22:26
 */
public class array_15 {
    /**
     * 解题思路：
     * 暴力破解法,定义一个相同的二维数组用于存储是否被访问，然后遍历数组，
     * 遇到0就直接返回，如果遇到1就让小岛数量加1，并且把该值的上下左右都是1的标记
     * 为已经访问的，这样就让再次访问到旁边的1就不会增加小岛数量值
     */
    //定义一个递归函数，作用就是把小岛周围的标记为是否已经访问
    private void help(char[][] g,boolean[][] visit,int i,int j){
        int m=g.length,n=g[0].length;
        //核心判断逻辑
        if(i<0||i>=m||j<0||j>=n||g[i][j]=='0'||visit[i][j])return;

        visit[i][j]=true;
        //就是把元素的上下左右如果都是1的话都标记为已经访问状态(i是上下，j是左右)
        help(g,visit,i-1,j);
        help(g,visit,i+1,j);
        help(g,visit,i,j-1);
        help(g,visit,i,j+1);
    }
    //Time:O(m*n) Space:O(m*n)
    public int solution(char[][] g){
        if(g==null||g.length==0||
        g[0]==null||g[0].length==0)return 0;

        int m=g.length,n=g[0].length;
        boolean[][] visit=new boolean[m][n];
        int num=0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(g[i][j]=='0'||visit[i][j])continue;
                ++num;
                help(g,visit,i,j);
            }
        }
        return num;
    }

    public static void main(String[] args) {
        int[][] a=new int[][]{{1,2},{3,4},{5,6}};
        System.out.println(a.length);
    }
}
